<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="libman.css">
<TITLE>
Writing Good CHR Programs
</TITLE>
</HEAD>
<BODY >
<A HREF="libman048.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="libman042.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="libman050.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc92">8.7</A>&nbsp;&nbsp;Writing Good <FONT COLOR=purple>CHR</FONT> Programs</H2><UL>
<LI><A HREF="libman049.html#toc45">Choosing <FONT COLOR=purple>CHR</FONT>s</A>
<LI><A HREF="libman049.html#toc46">Optimizations</A>
</UL>

This section gives some programming hints. For maximum efficiency of
your constraint handler, see also the subsection on options,
especially on <TT>check_guard_bindings</TT><A NAME="@default263"></A> and the <TT>debug_compile</TT><A NAME="@default264"></A><A NAME="@default265"></A><A NAME="@default266"></A>
flag.<BR>
<BR>
<A NAME="toc45"></A>
<H3 CLASS="subsection"><A NAME="htoc93">8.7.1</A>&nbsp;&nbsp;Choosing <FONT COLOR=purple>CHR</FONT>s</H3>
Constraint handling rules for a given constraint system can often be
derived from its definition in formalisms such as inference rules,
rewrite rules, sequents, formulas expressing axioms and theorems.
<FONT COLOR=purple>CHR</FONT>s can also be found by first considering
special cases of each constraint and then looking at interactions of
pairs of constraints sharing a variable. Cases that don't occur in the
application can be ignored.
<FONT COLOR=purple>CHR</FONT>s can also improve application programs by turning
certain predicates into constraints to provide &#8220;short-cuts&#8221;
(lemmas). For example, to the predicate <TT>append/3</TT> one can add
<TT>append(L1,[],L2) &lt;=&gt; L1=L2</TT> together with <TT>label_with</TT><A NAME="@default267"></A><TT>
append(L1,L2,L3) if true</TT>. <BR>
<BR>
Starting from an executable specification, the rules can then be
refined and adapted to the specifics of the application. <EM>Efficiency can be improved</EM> by strengthening or weakening the guards to
perform simplification as early as needed and to do the &#8220;just right&#8221;
amount of propagation. Propagation rules can be expensive, because no
constraints are removed. If the speed of the final handler is not
satisfactory, it can be rewritten using meta-terms or auxiliary C
functions.<BR>
<BR>
The rules for a constraint can be scattered across the <TT>chr</TT> file
as long as they are in the same module.
The rules are tried in <EM>some order</EM> determined by
the <FONT COLOR=purple>CHR</FONT> compiler. Due to optimizations this order is not necessarily
the textual order in which the rules where written. In addition, the
incremental addition of constraints at run-time causes constraints to
be tried for application of rules in some dynamically determined
order.<BR>
<BR>
<A NAME="toc46"></A>
<H3 CLASS="subsection"><A NAME="htoc94">8.7.2</A>&nbsp;&nbsp;Optimizations</H3>
Single-headed rules should be preferred to two-headed rules which
involve the expensive search for a partner constraint.
Rules with <EM>two heads can be avoided</EM> by changing the &#8220;granularity&#8221; of
the constraints. For example, assume one wants to express that <EM>n</EM>
variables are different from each other. It is more efficient to have
a single constraint <TT>all_different(List_of_n_Vars)</TT> than
<I>n</I><SUP>2</SUP>
inequality constraints (see handler <TT>domain.chr</TT>). However, the
extreme case of having a single constraint modelling the whole
constraint store will usually be inefficient.<BR>
<BR>
<EM>Rules with two heads</EM> are more efficient, if the two heads of the
rule share a variable (which is usually the case). Then the search for
a partner constraint has to consider less candidates. Moreover, two
rules with identical (or sufficiently similar) heads can be merged
into one rule so that the search for a partner constraint is only
performed once instead of twice.<BR>
<BR>
<EM>Rules with more than two heads</EM> are not allowed for efficiency
reasons. If needed, they can usually be written as several rules with
two heads. For example, in the handler for set constraints <TT>set.chr</TT>, the propagation rule:
<PRE CLASS="verbatim">
set_union(S1, S2, S), set(S1, S1Glb, S1Lub), set(S2, S2Glb, S2Lub) ==&gt;
        s_union(S1Glb, S2Glb, SGlb),
        s_union(S1Lub, S2Lub, SLub),
        set(S, SGlb, SLub).
</PRE>is translated into:
<PRE CLASS="verbatim">
set_union(S1, S2, S), set(S1, S1Glb, S1Lub) ==&gt;
        '$set_union'(S2, S1, S1Glb, S1Lub, S).
set(S2, S2Glb, S2Lub) \ '$set_union'(S2, S1, S1Glb, S1Lub, S) &lt;=&gt;
        s_union(S1Glb, S2Glb, SGlb),
        s_union(S1Lub, S2Lub, SLub),
        set(S, SGlb, SLub).
</PRE>
As <EM>guards</EM><A NAME="@default268"></A> are tried frequently, they should be
simple <EM>tests</EM> not involving side-effects. For efficiency and
clarity reasons, one should also avoid using user-defined constraints
in guards. Currently, besides conjunctions, disjunctions are allowed
in the guard, but they should be used with care. The use of other
control built-in predicates of ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> is discouraged. Negation and
if-then-else can be used if their first arguments are either <EM>simple goals</EM> (see ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> user manual) or goals that don't touch
global variables. Similarly, goals preceding a cut must fulfil this
condition.
<EM>Built-in constraints</EM> (e.g. finite domains, rational arithmetic)
work as tests only in the current implementation. 
Head matching is more efficient than
explicitly checking equalities in the guard (which requires the <TT>check_guard_bindings</TT><A NAME="@default269"></A> flag to be on). 
In the current
implementation, local variables (those
that do not occur in the heads) can be shared between the guard and
the body. <BR>
<BR>
<EM>Several handlers can be used simultaneously if</EM> they don't share
user-defined constraints. The current implementation will not work
correctly if the same constraint is defined in rules of different
handlers that have been compiled separately. In such a case, the
handlers must be merged &#8220;by hand&#8221;. This means that the source code
has to be edited so that the rules for the shared constraint are
together (in one module). Changes may be necessary (like
strengthening guards) to avoid divergence or loops in the computation.<BR>
<BR>
<EM>Constraint handlers</EM> can be tightly integrated with constraints
defined with <EM>other extensions of ECL</EM><SUP><EM><I>i</I></EM></SUP><EM>PS</EM><SUP><EM><I>e</I></EM></SUP> (e.g. meta-terms) by using
the ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> built-in predicate <TT>notify_constrained(Var)</TT> to notify
ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> each time a variable becomes more constrained.
This happens if a user-defined constraint is called for the first time
or if a user-defined constraint is rewritten by a <FONT COLOR=purple>CHR</FONT> into a stronger
constraint with the same functor.<BR>
<BR>
For <EM>pretty printing</EM> of the user-defined constraints in the answer at
the top-level and debuggers, ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> macro transformation (for write
mode) can be used. This is especially useful when the constraints
have some not so readable notation inside the handler. For an
example, see the constraint handler bool <TT>bool.chr</TT>.<BR>
<BR>
<HR>
<A HREF="libman048.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="libman042.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="libman050.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
